package exec;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @Description 排序数组中两个数字之和
 * @Date 2022/11/1 10:01
 * @Created by wangjun
 */
public class TwoSum {

    /**
     * 功能描述: 给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
     * <p>
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
     * <p>
     * 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
     *
     * @Param: [numbers, target]
     * @Return: int[]
     */
    public static int[] twoSum(int[] numbers, int target) {
        if (numbers.length == 0) {
            return null;
        }
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (target - numbers[i] == numbers[j]) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    /**
     * 功能描述: 采用map存储
     *
     * @Param: [numbers, target]
     * @Return: int[]
     */
    public static int[] twoSum1(int[] numbers, int target) {
        if (numbers.length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>(numbers.length);
        for (int i = 0; i < numbers.length; i++) {
            int divide = target - numbers[i];
            if (map.containsKey(divide)) {
                return new int[]{map.get(divide), i};
            }
            map.put(numbers[i], i);
        }
        return null;
    }

    public static int[] twoSum2(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int middle = (high - low) / 2 + low;
                if (target - numbers[i] == numbers[middle]) {
                    return new int[]{i, middle};
                } else if (target - numbers[i] < numbers[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    public static int[] twoSum3(int[] numbers, int target) {
        if (numbers.length == 0) {
            return new int[]{-1, -1};
        }
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int middle = (high - low) / 2 + low;
                if (target - numbers[middle] == numbers[i]) {
                    return new int[]{i, middle};
                } else if (target - numbers[i] < numbers[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    public static int[] towSum4(int[] numbers, int target) {
        if (numbers.length == 0) {
            return new int[]{-1, -1};
        }
        int low = 0, high = numbers.length - 1;
        while (low <= high) {
            int sum = numbers[low] + numbers[high];
            if (target == sum) {
                return new int[]{low, high};
            } else if (sum < target) {
                low++;
            } else {
                high--;
            }
        }
        return new int[]{-1, -1};
    }

    public static int[] towSum5(int[] numbers, int target) {
        if (numbers.length == 0) {
            return new int[]{-1, -1};
        }
        int low = 0, high = numbers.length - 1;
        while (low <= high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{numbers[low], numbers[high]};
            }
            if (sum < target) {
                low++;
            } else {
                high--;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] ints = towSum5(new int[]{0, 0, 3, 4}, 4);
        System.out.println(Arrays.toString(ints));
    }
}
